package sort.leetcode_1122_easy_costume_sort;

import java.util.HashMap;
import java.util.Map;

/**
 * LeetCode1122题, 数组的相对排序
 * <p>
 * 给你两个数组，arr1 和 arr2，
 * 1. arr2 中的元素各不相同
 * 2. arr2 中的每个元素都出现在 arr1 中
 * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 */
public class RelativeSortArray {
    public static void main(String[] args) {
        int[] arr1 = new int[]{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};
        int[] arr2 = new int[]{2, 1, 4, 3, 9, 6};
        int[] array = new RelativeSortArray().relativeSortArray(arr1, arr2);
        printArray(array);
    }

    /**
     * 根据arr2中的每个元素都出现在arr1中这个条件，就是说，只需要对arr1这个数组进行排序即可，只是需要特殊的排序方式。
     * <p>
     * 排序规则：
     * 1. 在arr1中的出现的元素，但是没在arr2中出现的元素，升序排列
     * 2. arr1中所有出现在arr2中的元素，保存原顺序，且保证相对位置不变。
     * <p>
     * 根据 arr2 中的每个元素都出现在 arr1 中 这个条件，可以利用哈希表，K：arr2中元素的值 V：arr2中元素的值的出现位置。
     * 这样在哈希表中就保留了arr2中所有元素的相对位置。
     * <p>
     * 分析所有可能出现的情况：（只需要对arr1中的元素进行排序），对arr1中的任意两个元素 x , y 有如下情况
     * 1. x,y 都出现在arr2中，此时保留两者的相对位置即可，可类比为，靠前的数更小。（只是位置关系，与值没关系）
     * 2. x,y 只有一个出现在arr2中，先出现的 更小，返回true;
     * 3. x,y 都不存在与arr2中，直接比较两个数大小即可。
     * <p>
     * 以这三种情况来编写自定义排序的函数，
     * 该函数的要求：只有 x（值） < y（值） 才返回true;
     * 该函数的作用：通过上述三种可能性，比较 x 和 y 的大小。
     */
    public boolean less(int x, int y) {
        //如果x, y 都出现在arr2中，直接比较对应位置
        if (record.containsKey(x) && record.containsKey(y)) {
            //在数组中，靠前的位置更小。
            return record.get(x) <= record.get(y);
        } else if (record.containsKey(x)) {
            //如果只有1个出现在arr2中， 先出现的更小，x先出现说明 x < y
            return true;
        } else if (record.containsKey(y)) {
            //先出现y，说明 x > y 不符合排序规则
            return false;
        } else {
            /*
                x,y都没出现在arr2中，那么按照题目要求： 未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
                直接比较x,y的大小
             */
            return x <= y;
        }
    }

    /*
        有了自定义的排序函数后，就可以用使用各种排序算法了，只是在比较时，换成自定义的排序函数，按我们想要的方式排列即可。
     */
    Map<Integer, Integer> record;

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        record = new HashMap<>(arr2.length);
        // 值 --> 索引位置
        for (int i = 0; i < arr2.length; i++) {
            record.put(arr2[i], i);
        }
//        quickSort(arr1,0,arr1.length - 1);
        mergeSort(arr1);
        return arr1;
    }

    //冒泡排序
    public void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        boolean flag = true;
        int N = arr.length;
        for (int i = N - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                /*
                    自定义排序函数的功能，前面的参数 < 后面的参数
                    也就是arr[j] < arr[j + 1]
                    那么就要修改比较顺序，因为冒泡排序中 如果arr[j] < arr[j + 1]的话 是降序的。

                    而题目要求升序。所以就要反过来比较。
                if (less(arr[j], arr[j + 1])) {
                    swap(arr, j, j + 1);
                }
                 */
                if (less(arr[j + 1], arr[j])) {
                    swap(arr, j + 1, j);
                    flag = false;
                }
            }
            if (flag) {
                return;
            }
        }
    }

    //选择排序
    public void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int i = 0; i < N - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < N; j++) {
                if (less(arr[j], arr[minIndex])) {
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                swap(arr, minIndex, i);
            }
        }
    }

    //插入排序
    public void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0; j--) {
                if (less(arr[j], arr[j - 1])) {
                    swap(arr, j, j - 1);
                }
            }
        }
    }

    //希尔排序
    public void shellSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        int increment = 0;
        while (increment < N / 3) {
            increment = increment * 3 + 1;
        }
        while (increment > 0) {
            for (int i = increment; i < N; i++) {
                for (int j = i; j >= increment; j -= increment) {
                    if (less(arr[j], arr[j - increment])) {
                        swap(arr, j, j - increment);
                    }
                }
            }
            increment /= 3;
        }
    }

    //归并排序
    public void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int[] helper = new int[arr.length];
        sort(arr, helper, 0, arr.length - 1);
    }

    public void sort(int[] arr, int[] helper, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(arr, helper, lo, mid);
        sort(arr, helper, mid + 1, hi);
        merge(arr, helper, lo, mid, hi);
    }

    public void merge(int[] arr, int[] helper, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            helper[i] = arr[i];
        }
        int left = lo, right = mid + 1;
        for (int i = lo; i <= hi; i++) {
            if (left > mid) {
                arr[i] = helper[right++];
            } else if (right > hi) {
                arr[i] = helper[left++];
            } else if (less(helper[left], helper[right])) {
                arr[i] = helper[left++];
            } else {
                arr[i] = helper[right++];
            }
        }
    }

    //快速排序
    public void quickSort(int[] arr, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int pivotIndex = partition(arr, lo, hi);
        quickSort(arr, lo, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, hi);
    }

    public int partition(int[] arr, int lo, int hi) {
        int pivot = arr[lo];
        int left = lo;
        int right = hi;
        while (left != right) {
            while (left < right && less(pivot, arr[right])) {
                right--;
            }
            while (left < right && less(arr[left], pivot)) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        arr[lo] = arr[left];
        arr[left] = pivot;
        return left;
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
